#include <bits/stdc++.h>

using namespace std;

// 回文子串数量
// 返回字符串s的回文子串数量
// 测试链接 : https://leetcode.cn/problems/palindromic-substrings/

class Solution 
{
public:
    static const int MAXN = 1001;
    char ss[MAXN << 1];
    int p[MAXN << 1];
    int n;

    void manacherss(string& s)
    {
        n = s.size() * 2 + 1;
        for(int i = 0, j = 0; i < n; ++i)
        {
            ss[i] = (i & 1) == 0 ? '#' : s[j++];
        }
    }

    void manacher(string& s)
    {
        manacherss(s);
        for(int i = 0, r = 0, c = 0, len; i < n; ++i)
        {
            len = r > i ? min(p[2 * c - i], r - i) : 1;
            while(i + len < n && i - len >= 0 && ss[i + len] == ss[i - len])
            {
                ++len;
            }
            if(i + len > r)
            {
                r = i + len;
                c = i;
            }
            p[i] = len;
        }
    }

    int countSubstrings(string s) 
    {
        manacher(s);
        int ans = 0;
        for(int i = 0; i < n; ++i) ans += p[i] / 2;
        return ans;
    }
};


class Solution 
{
public:
    int countSubstrings(string s) 
    {
        int n = s.size();
        int ans = 0;
        for(int i = 0; i < 2 * n - 1; ++i)
        {
            int l = i / 2, r = i / 2 + i % 2;
            while(l >= 0 && r < n && s[l] == s[r])
            {
                --l, ++r, ++ans;
            }
        }
        return ans;
    }
};